package solution._0000._0005;

/**
 * Created by chen_snow
 * Date: 2021/5/5 12:20
 * Description: 最长回文子串 给你一个字符串 s，找到 s 中最长的回文子串。
 */
public class Solution {

    public static void main(String[] args) {
        longestPalindrome("babad");
    }

    public static String longestPalindrome(String s) {
        int[][] data = new int[s.length()][s.length()];

        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j < s.length(); j++) {
                data[i][j] = 0;
            }
        }

        for (int i = 0; i < s.length(); i++) {
            data[i][i] = 1;
        }

        for (int column = 1; column < s.length(); column++) {
            for (int row = column - 1; row >= 0; row--) {
                fillData(s, row, column, data);
            }
        }

        int row = 0, column = 0, result = 0;
        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j < s.length(); j++) {
                if (data[i][j] > result) {
                    row = i;
                    column = j;
                    result = data[i][j];
                }
            }
        }

        return s.substring(row, column + 1);

    }

    public static void fillData(String s, int row, int column, int[][] data) {
        char rowCh = s.charAt(row);
        char columnCh = s.charAt(column);

        if (column - row == 1) {
            data[row][column] = rowCh == columnCh ? 2 : 0;
            return;
        }

        if (rowCh == columnCh) {
            data[row][column] = data[row + 1][column - 1] == 0 ? 0 : data[row + 1][column - 1] + 2;
        } else {
            data[row][column] = 0;
        }
    }
}
